package code1.binary_tree;

/**
 * 原题链接：https://leetcode.cn/problems/trim-a-binary-search-tree/
 */
public class P669 {

    public void travel(TreeNode cur,TreeNode pre,int low,int high){
        if(cur==null){
            return;
        }
        if(cur.val>=low && cur.val<=high){      //没超出边界
            travel(cur.left,cur,low,high);
            travel(cur.right,cur,low,high);
        }else if(cur.val>high){                 //超出右边界
            if(cur.left==null && cur.right==null){      //说明是叶节点
                if(pre.left==cur) pre.left=null;
                if(pre.right==cur) pre.right=null;
            }else{
                travel(cur.left,cur,low,high);          //不是叶节点，其左子树可能在范围内
                if(pre.left==cur) pre.left=cur.left;
                if(pre.right==cur) pre.right=cur.left;
            }
        }else if(cur.val<low){                  //超出左边界
            if(cur.left==null && cur.right==null){      //说明是叶节点
                if(pre.left==cur) pre.left=null;
                if(pre.right==cur) pre.right=null;
            }else{
                travel(cur.right,cur,low,high);     //不是叶节点，其右子树可能在范围内
                if(pre.left==cur) pre.left=cur.right;
                if(pre.right==cur) pre.right=cur.right;
            }
        }
    }

    public TreeNode trimBST_(TreeNode root, int low, int high) {
        if(root==null) return root;
        if(root.val>=low && root.val<=high){
            travel(root.left,root,low,high);
            travel(root.right,root,low,high);
        }else if(root.val>high){
            if(root.left==null && root.right==null){
                root=null;
            }else{
                travel(root.left,root,low,high);
                root=root.left;
            }
        }else if(root.val<low){
            if(root.left==null && root.right==null){
                root=null;
            }else{
                travel(root.right,root,low,high);
                root=root.right;
            }
        }
        return root;
    }

    //精简版
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root==null){
            return null;
        }
        if(root.val>high){      //超出右边界
            return trimBST(root.left,low,high);     //返回左子树修剪后的子树
        }
        if(root.val<low){       //超出左边界
            return trimBST(root.right,low,high);    //返回右子树修剪后的子树
        }
        //边界内
        root.left=trimBST(root.left,low,high);
        root.right=trimBST(root.right,low,high);
        return root;
    }
}
